package com.aqie.easy.array;

/**
 * 581 最短无序连续子数组 todo
 */
public class FindUnsortedSubarray {
    /**
     * 左边界：左侧都比他小，右侧存在比他大的
     * 右边界：右侧都比他大,左侧存在比他小的
     * @param nums
     * @return
     */
    public static int findUnsortedSubarray(int[] nums) {
        int s = -1;
        int e = -1;
        for(int i = 0; i < nums.length - 1; i++){
            if(nums[i] > nums[i + 1]){
                s = i;
                break;
            }
        }
        while(s > 0 && nums[s] == nums[s - 1]) s--;

        if(s == -1) return 0;
        for(int i = nums.length - 1; i > 0; i--){
            if(nums[i] < nums[i - 1]){
                e = i;
                break;
            }
        }
        while(e < nums.length - 1 && nums[e] == nums[e + 1]) e++;

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i = s; i <= e; i++){
            if(min > nums[i])
                min = nums[i];
            if(max < nums[i])
                max = nums[i];
        }
        int res_s = -1, res_e = -1;
        for(int i = 0; i <= s; i++){
            if(nums[i] > min){
                res_s = i;
                break;
            }
        }
        for(int i = nums.length - 1; i >= e; i--){
            if(nums[i] < max){
                res_e = i;
                break;
            }
        }
        return res_e - res_s + 1;


    }

    public static int findUnsortedSubarray2(int[] nums){
        int high = 0;
        int low = 1;
        int maxValue = 0;
        int minValue = 0;

        for (int i =0; i < nums.length; i++){
            if (i == 0) {
                maxValue = nums[i];
            }else {
                if (nums[i] < maxValue) {
                    high = i;
                }
                maxValue = Math.max(maxValue, nums[i]);
            }
        }

        for (int i = nums.length - 1; i >= 0; i--){
            if (i == nums.length - 1){
                minValue = nums[i];
            }else {
                if (nums[i] > minValue){
                    low = i;
                }
                minValue = Math.min(minValue, nums[i]);
            }
        }
        return high - low + 1;
    }


    public static void main(String[] args) {
        // int[] arr = {2, 6, 4, 8, 10, 9, 15};         // 5
        // int[] arr = {1,2,3,4,5,4,2};                 // 5
        // int[] arr = {1,3,2,2,2};                     // 4
        int[] arr = {2,2,2,1};
        // int[] arr = {1,2,3,3,3};                           // 0 0 0
        // int[] arr = {2,1,3,3,3};                           // 0 1 2
        // int[] arr = {2,1,2,3,3,3};                        //  0 1 2
        System.out.println(findUnsortedSubarray(arr));
    }
}
